//#include <stdio.h>
//#include <stdbool.h>
//
//#define MAX_N 200000
//
//int f[MAX_N + 10];
//int primes[MAX_N + 10];
//bool is_prime[MAX_N + 10];
//
//void precompute() 
//{
//    int cnt = 0;
//    for (int i = 2; i <= MAX_N; i++)
//    {
//        is_prime[i] = true;
//    }
//    for (int i = 2; i <= MAX_N; i++)
//    {
//        if (is_prime[i]) 
//        {
//            primes[cnt++] = i;
//            f[i] = 1;
//        }
//        for (int j = 0; j < cnt && i * primes[j] <= MAX_N; j++) 
//        {
//            is_prime[i * primes[j]] = false;
//            f[i * primes[j]] = f[i] + 1;
//            if (i % primes[j] == 0) 
//            {
//                break;
//            }
//        }
//    }
//}
//
//int main() {
//    precompute();
//    int T;
//    scanf_s("%d", &T);
//    while (T--) {
//        int x;
//        scanf_s("%d", &x);
//        printf("%d\n", 2 * f[x]);
//    }
//    return 0;
//}

//#include <stdio.h>
//#include <stdbool.h>
//
//#define MAXN 1000000   
//
//static bool isPrime[MAXN + 1];
//
//static void buildPrimeTable(void)
//{
//    for (int i = 0; i <= MAXN; ++i)
//        isPrime[i] = true;
//
//    isPrime[0] = isPrime[1] = false;
//
//    for (int i = 2; i * i <= MAXN; ++i)
//    {
//        if (isPrime[i])
//        {
//            for (int j = i * i; j <= MAXN; j += i)
//                isPrime[j] = false;
//        }
//    }
//}
//
//int main(void)
//{
//    buildPrimeTable(); 
//
//    int T;
//    if (scanf_s("%d", &T) != 1) return 0;
//
//    while (T--)
//    {
//        int n;
//        scanf_s("%d", &n);
//        puts(isPrime[n] ? "Yes" : "No");
//    }
//
//    return 0;
//}

#include <stdio.h>
#include <stdbool.h>

#define MAXN 1000000 

static bool isPrime[MAXN + 1];

static void buildPrimeTable(void)
{
    for (int i = 0; i <= MAXN; ++i)
        isPrime[i] = true;

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= MAXN; ++i)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= MAXN; j += i)
                isPrime[j] = false;
        }
    }
}

int main(void)
{
    buildPrimeTable(); 

    int T;
    if (scanf_s("%d", &T) != 1) return 0;

    while (T--)
    {
        int n;
        scanf_s("%d", &n);
        puts(isPrime[n] ? "Yes" : "No");
    }

    return 0;
}